package com.leetcode.solution.s9x;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetsWithDup90 {
    public static void main(String[] args) {
        int[] nums = new int[]{4,4,4,1,4};
        List<List<Integer>> result = new SubsetsWithDup90().subsetsWithDup(nums);
        for (List<Integer> integers : result) {
            for (Integer integer : integers) {
                System.out.print(integer + ", ");
            }
            System.out.println();
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();
        dfs(false, 0, nums, subsets, subset);

        return subsets;
    }

    private void dfs(boolean choosePre, int curr, int[] nums, List<List<Integer>> subsets, List<Integer> subset) {
        // 最后一个
        if (curr == nums.length) {
            subsets.add(new ArrayList<>(subset));
            return;
        }

        // 不包含情况
        dfs(false, curr + 1, nums, subsets, subset);

        // 包含情况
        if (!choosePre && curr > 0 && nums[curr - 1] == nums[curr]) {
            return;
        }

        subset.add(nums[curr]);
        dfs(true, curr + 1, nums, subsets, subset);
        subset.remove(subset.size() - 1);
    }


}
